Ramsey numbers quantify how big a graph can get before it necessarily contains a certain kind of substructure

For example, imagine you’ve got six vertices, each connected to every other vertex by edges. Now color each of the 15 total edges either red or blue. No matter how you apply the colors, it’s inevitable that you’ll end up with three vertices that are all connected to each other by edges of the same color (known as a “clique”). The same is not true, however, if you start with five vertices (for which it’s possible to do the coloring without creating a clique). As a result, mathematicians say that the Ramsey number for two colors and a clique of size 3 is 6 — meaning you need at least six vertices to guarantee the clique exists.

original file:: [[tickler-2020-12]] topic:: [[graph theory]] via:: MIT Undergraduate Math Student Pushes Frontier of Graph Theory | Quanta Magazine